package code2101_2200.code80_90;

import java.util.ArrayDeque;

/**
 * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
 *
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 *
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 */
public class _2185isSymmetric {

    // 思考 ： 双栈思路，一个从左到右入栈，一个从右到左入栈

    /**
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 7.10%     * 的用户
     * 内存消耗：     * 37.6 MB     * , 在所有 Java 提交中击败了     * 6.32%     * 的用户
     *
     * 这个效率得看题解解决了！
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null))return true;
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>();
        ArrayDeque<TreeNode> stack2 = new ArrayDeque<>();
        TreeNode node1;
        TreeNode node2;
        stack1.addFirst(root);
        stack2.addFirst(root);
        while (!stack1.isEmpty()&&!stack2.isEmpty()){
            node1 = stack1.pollFirst();
            node2 = stack2.pollFirst();
            if(node1.val!=node2.val)return false;
            if(node1.left!=null&&node2.right!=null){
                stack1.addFirst(node1.left);
                stack2.addFirst(node2.right);
            }else if(node1.left!=null||node2.right!=null)return false;

            if(node1.right!=null&&node2.left!=null){
                stack1.addFirst(node1.right);
                stack2.addFirst(node2.left);
            }else if(node1.right!=null||node2.left!=null)return false;

            if(node1.left==null&&node2.left==null&&node1.right==null&&node2.right==null){
                continue;
            }
        }
        return true;
    }

    /**
     * 题解 递归 更优美一点
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 36.3 MB     * , 在所有 Java 提交中击败了     * 66.87%     * 的用户
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }

}
